\documentclass[11pt]{article}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
%\geometry{landscape}                % Activate for for rotated page geometry
%\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage[all]{xy}
\usepackage{epstopdf}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}

\title{Core Language Nan0Scala}
%\date{}                                           % Activate to display a given date or no date

\begin{document}

\section{Syntax}\label{Grammar}
\begin{align*}
prog~&::=~constr^{0\ldots l}~ob^{0\ldots k}~cd^{0\ldots n}~e \\
ob~&::=~\textbf{object}~O~\{~extr~\}\\
extr~&::=~\textbf{def}~\textbf{unapply}(x~:~C)~:~extpe~=~e~ \\
extpe~&::=~\textbf{Option}[~(D^{1\ldots n})~]~|~\textbf{Boolean}~ \\
cd~&::=~cc~|~ac~ \\
cc~&::=~\textbf{class}~C(\textbf{val}~f^{0\ldots n}:C^{0\ldots n})~\textbf{extends}~D~\{~md^{0 \ldots k}~\}\\
ac~&::=~\textbf{abstract class}~C(\textbf{val}~f^{0\ldots n}:C^{0\ldots n})~\textbf{extends}~D~\{~md^{0 \ldots k}~\}\\
md~&::=~\textbf{def}~\texttt{m}(x^{0 \ldots n}:~C^{0 \ldots n})~:~C~=~e~ \\
e ~&::=~se~|~(se:C)~\textbf{match}~\{~c^{0\ldots n}~\}~|~(~e~)~|~\\
&\quad\quad~\textbf{if}~(~se~)~\{~e~\}~\textbf{else}~\{~e~\}~\\
se~&::=~\texttt{x}~|~\textbf{new}~C(se^{0\ldots n})~|~se.\texttt{m}(se^{0 \ldots n})~|~se.\texttt{f}~|~\\
&\quad\quad~be~|~se~aop~se~|~se.\textbf{isInstanceOf}[C]\\
c~&::=~\textbf{case}~p~gd~\Rightarrow~e\\
p~&::=~\texttt{x}:C~|~ C(p^{0\ldots n}) \\
gd~&::=~\textbf{if}~be~|~\epsilon \\
be~&::=~se~bop~be~|~se~bop~se\\
bop~&::=~!=~|~<~|~<=~|~>~|~>=~|~==~|~\&\&~|~||~\\
aop~&::=~+~|~-~|~*~|~/~|~\% \\
constr~&::=~\textbf{/* constraints of }~D~:~fm~\textbf{*/}~\\
fm~&::=~at~\&~at~~|~~at~|~at~~|~~at~~|~~(~at~)\\
at~&::=~t~<:~t \\
t~&::=~un~|~int~|~el~\\
un~&::=~t~+~t~|~el~\\
int~&::=~t~*~t~|~el~\\
el~&::=~\texttt{X}~|~\textbf{empty}~\\
\end{align*}

\subsection{Predefined Type, Built-in Type and Values}

\textbf{Object} is the root class of any declared class. \textbf{Int} and \textbf{Boolean} are the two predefined types of the language. Additionally we have the built-in types \textbf{Option}, \textbf{Some}, \textbf{None} and \textbf{TupleN} (where N is any integer number greater than 0) that are needed by the extractors. \textbf{None} is not really a type because it is declared as \textbf{object} in Scala, hence we will use it just as a value of the language. Therefore, a value in the language is an invocation expression (\textbf{new C (...)}), \textbf{None}, \textbf{true}, \textbf{false}, any integer number and \textbf{wrong} (that would be internally used to propagate an error).\\

As long as in the program we don't use any reserved Scala keywords, any program written in this language is a valid Scala program.



\subsection{Some Note}
Each program source is composed by a list of constraint, a list of object declaration, a list of class declaration and, finally, an expression that is the \emph{main} of the program. 

Each object (must) contains only the unapply method definition. Hence, an object is just a container for an extractor (no more than one extractor). The return type of an extractor can be either an Option type (that take some TupleN type) or Boolean (this because Option[()] is not defined in Scala, and if we want to state that any program written in our language is a valid Scala program, then we need to use Boolean type). 

A class can be either abstract or concrete. The only difference is dictated by the operational semantic (as an abstract class can't be invoked for an object creation). We need abstract class in order to have credible pattern matching expression (as in any code that use pattern matching we have that the root class of the matching expression is abstract) and also because we can derive a very important axiom for proving completeness (e.g. Tree $<:$ Leaf + Node, when class Tree is abstract).

About expression (statements) the only particularity is that we don't want to allow to have some expression (e.g. pattern matching, if then else, object creation) inside the guard of a matching case (if we want to have that then we still need have t define how we want to handle these situations ...). The same goes for the if in the condition (as we can think about if statements as a pattern matching expression, and this is probably how it is going to be translated... in such a way that if statement is just syntactic sugar of the language). This should explain why we have, in the grammar, the creation rule \emph{se} (that stand for "simple expression") 

The predefined type of the language are Boolean and Integer. Then we also need the built-in types Option and Tuple2, Tuple3, \ldots, TupleN (all these are needed for the return type of the unapply method).

About the user-defined constraints, symbol $<:$ stands for subseteq, + for union, * for intersection. Keyword \textbf{empty} stands for $\emptyset$ and \texttt{X} is the identifier of a class or an object in the source code.


If I forgot to mention something, or if there is anything missing (I hope not) or if something doesn't make sense... let me know

\end{document}  